package com.hch.algorithm.stack;

/**
 * Created by Hzc on 2019/1/29.
 * 栈的可能实现方式与队列相同，可以是数组实现、顺序表实现、链表实现
 * 最简单的实现方式是链表实现，但空间浪费比较大
 * 最复杂的实现方式是数组/顺序表实现，当数据量比较大时可以很好地节约内存空间
 * 这里采用数组实现，实现的思想参考下面代码中的注释
 * 另外两种实现方式不写
 *
 * 栈需要实现的方法：
 * 　　isEmpty()：判断栈是否为空。栈为空的条件：栈顶索引 top 为 0。
 * 　　isFull()：判断栈是否满。这个方法只有数组实现才需要，链式实现不需要。栈满的条件：栈顶索引 top 为 MAXSIZE。
 * 　　clear()：清空栈。清空方法：将栈顶索引 top 设置为 0。
 * 　　push(T)：将数据入栈。入栈方法：先将数据放到栈顶索引 top 处，再将栈顶索引 top + 1。
 * 　　pop()：将栈顶数据出栈。出栈方法：先将栈顶索引 top - 1，再将栈顶数据返回。
 * 　　top()：返回栈顶数据，但不将栈顶数据出栈。
 * 　　height()：获取栈的高度。栈顶索引的大小即为栈顶高度。
 * 需要注意的是：我实现时，栈顶索引比实际栈顶的索引要大1。例如，栈顶索引 top=1时，实际栈顶为stack[0]，此时栈里只有这一个元素。
 */
public class Stack <T> {
    /**
     * stack：用作栈的数组
     * MAXSIZE：栈的最大高度
     * top：栈顶索引
     */
    private T[] stack;//用作队列的数组
    private static final int MAXSIZE = 20;//栈的最大高度
    private int top;//栈顶索引
 
    /**
     * 两种构造方法
     */
    public Stack(){//默认空构造方法
        stack = (T[]) new Object[MAXSIZE];
        top = 0;//初始时，栈顶为 0
    }
 
    public Stack(T[] list){//根据元素列表构造栈的构造方法
        stack = list;
        top = list.length-1;//初始时，栈顶为列表的最后一个元素
    }
 
    /**
     * 判断栈是否为空
     * @return 栈是否为空
     */
    public boolean isEmpty(){
        if ((top == 0))//栈空的条件：栈最底处为空
            //链表实现时，栈空的条件：链表头为空
            return true;
        return false;
    }
 
    /**
     * 判断栈是否满
     * @return 栈是否满
     */
    public boolean isFull(){
        if (top == MAXSIZE)//栈满的条件：栈顶到达数组最末端
            //一般情况下，链表不存在栈满的情况
            return true;
        return false;
    }
 
    /**
     * 清空栈
     */
    public void clear(){
        if (isEmpty())
            return;
        top = 0;//将栈顶索引移动到 0 处
    }
 
    /**
     * 将数据入栈
     * @param data：需要入栈的数据
     * @return 入栈是否成功
     */
    public boolean push(T data){
        if (isFull())//栈满，不能入栈
            return false;
        else
            stack[top++] = data;//把数据放入新栈顶索引位置，再将栈顶索引递增 1
        return true;
    }
 
    /**
     * 将栈顶数据出栈
     * @return 出栈的数据
     */
    public T pop(){
        if (isEmpty())//栈空，不能出栈
            return null;
        return stack[--top];
    }
 
    /**
     * 获取栈顶元素
     * @return 栈顶元素
     */
    public T top(){
        if (isEmpty())//栈空，没有元素
            return null;
        return stack[top-1];//返回栈顶数据即可
    }
 
    /**
     * 获取栈的高度
     * @return 栈的高度
     */
    public int height(){
        return top;//栈顶索引是实际栈顶索引+1，因此栈顶索引的大小即为栈的高度
        /**
         * 
         * +-------------+
         * |    null     |
         * |    null     |
         * |    null     | ← 栈顶索引 top = 1
         * |  data = 1   | ← 实际栈顶
         * +-------------+
         */
    }
 
    /**
     * 打印栈里的数据，仅用于测试
     */
    public void display(){
        System.out.print("从栈顶向栈底打印：");
        for (int i = top-1; i >= 0; i--) {
            System.out.print(" " + stack[i]);
        }
        System.out.println();
    }
}